package com.hc.programming.tree;

import java.util.*;

/**
 * 10
 * 7    15
 * 13  18
 * 交替输出二叉树: 奇数行从左到右，偶数行从右到左
 * 上图输出：[[10], [15,7], [13,18]]
 *
 * @author huangchao E-mail:fengquan8866@163.com
 * @version 创建时间：2024/6/17 21:06
 */
public class 交替顺序输出二叉树 {
    public static void main(String[] args) {
        TreeNode n13 = new TreeNode(13);
        TreeNode n18 = new TreeNode(18);
        TreeNode n7 = new TreeNode(7);
        TreeNode n15 = new TreeNode(15, n13, n18);
        TreeNode n10 = new TreeNode(10, n7, n15);

        // 方案一：递归缓存到map，再输出
//        mapCache(n10);

        // 方案二：List缓存再打印
        listCache(n10);
    }

    /**
     * 方案二：List缓存再打印
     */
    private static void listCache(TreeNode n10) {
        List<List<Integer>> list = new ArrayList<>();
        recursion2(n10, 0, list);
        for (int i = 0; i < list.size(); i++) {
            if (i % 2 == 1) {
                Collections.reverse(list.get(i));
            }
        }
        System.out.println(list);
    }

    private static void recursion2(TreeNode node, int level, List<List<Integer>> list) {
        if (list.size() <= level) {
            list.add(new ArrayList<>());
        }
        list.get(level).add(node.getVal());
        if (node.getLeft() != null) {
            recursion2(node.getLeft(), level + 1, list);
        }
        if (node.getRight() != null) {
            recursion2(node.getRight(), level + 1, list);
        }
    }

    /**
     * 方案一：递归缓存到map，再输出
     */
    private static void mapCache(TreeNode n10) {
        StringBuilder sb = new StringBuilder("[");
        // 方案一：map存储，再输出
        Map<Integer, List<Integer>> map = new HashMap<>();
        recursion(n10, 1, map);
        int size = map.size();
        for (int i = 1; i <= size; i++) {
            List<Integer> list = map.get(i);
            if (i % 2 == 0) {
                // 从右到左输出
                Collections.reverse(list);
            }
            sb.append(list).append(", ");
        }
        if (sb.length() > 2) {
            sb.delete(sb.length() - 2, sb.length());
        }
        sb.append("]");
        System.out.println(sb.toString());
    }

    private static void recursion(TreeNode node, int level, Map<Integer, List<Integer>> map) {
        List<Integer> list = map.computeIfAbsent(level, k -> new ArrayList<>());
        list.add(node.getVal());
        if (node.getLeft() != null) {
            recursion(node.getLeft(), level + 1, map);
        }
        if (node.getRight() != null) {
            recursion(node.getRight(), level + 1, map);
        }
    }
}
